lovasz theta function
The Lovász ϑ function, SVMs and finding large dense subgraphs
The Lovasz \theta function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms. Computing \theta involves solving a SDP and is extremely expensive even for moderately sized graphs. In this paper we establish that the Lovasz \theta function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM-\theta graphs, on which the Lovasz \theta function can be approximated well by a one-class SVM.